package 热题100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 热题39组合总和 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        热题39组合总和 o = new 热题39组合总和();
        int[] arr = {2,3,5};

        o.combinationSum(arr,8);
        for(List<Integer> list : o.res){
            System.out.println(list);
        }
    }



    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//先将数组升序排列
        help(candidates,target,candidates.length-1);//然后进行递归
        return res;//最终返回结果
    }

    public void help(int[] arr,int target,int index){
        if (target <= 0){//如果target <= 0 ,就不用在继续向下递归遍历
            res.add(new ArrayList<>(list));
            return;
        }

        //否则从index位置，开始遍历，使用贪心+回溯
        for (int i = index; i >= 0 ; i--) {
            //如果当前位置得元素，大于target，相减小于0，不符合，继续遍历，剪枝
            if (arr[i] > target) continue;

            //如果i和i-1相等，跳过i-1
            if (i > 0 && arr[i] == arr[i-1]) continue;

            //否则，将当前位置得元素添加到list中
            list.add(arr[i]);

            //继续进行当前位置i得遍历，因为一个元素可以多次选择，所以从i继续遍历
            help(arr,target-arr[i],i);

            //最后将当前添加位置得元素进行回溯
            list.remove(list.size()-1);
        }
    }
}
